<!DOCTYPE html>
<html>
<head><meta name="generator" content="Hexo 3.8.0">
  <meta charset="utf-8">
  
  <title>平衡二叉搜索树 | JAVA</title>
  <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
  
  <meta name="keywords" content="数据结构与算法">
  
  
  
  
  <meta name="description" content="平衡二叉搜索树平衡二叉搜索树简称:BBST 平衡二叉搜索树类型  AVL树 Windows NT 内核中广泛使用  红黑树 C++ STL(比如map、set) java的TreeMap、TreeSet、HashMap、HashSet Linux的进程调度 Ngix的timer管理   AVL树平衡因子(Balance Factor): 某节点的左右子树的高度差 特点 每个节点的平衡因子只可能是1">
<meta name="keywords" content="数据结构与算法">
<meta property="og:type" content="article">
<meta property="og:title" content="平衡二叉搜索树">
<meta property="og:url" content="https://jameslin23.gitee.io/2020/12/12/平衡二叉搜索树/index.html">
<meta property="og:site_name" content="JAVA">
<meta property="og:description" content="平衡二叉搜索树平衡二叉搜索树简称:BBST 平衡二叉搜索树类型  AVL树 Windows NT 内核中广泛使用  红黑树 C++ STL(比如map、set) java的TreeMap、TreeSet、HashMap、HashSet Linux的进程调度 Ngix的timer管理   AVL树平衡因子(Balance Factor): 某节点的左右子树的高度差 特点 每个节点的平衡因子只可能是1">
<meta property="og:locale" content="zh-CN">
<meta property="og:image" content="https://jameslin23.gitee.io/2020/12/12/%E5%B9%B3%E8%A1%A1%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91/image-20201212141626132.png">
<meta property="og:image" content="https://jameslin23.gitee.io/2020/12/12/%E5%B9%B3%E8%A1%A1%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91/image-20201212142308077.png">
<meta property="og:image" content="https://jameslin23.gitee.io/2020/12/12/%E5%B9%B3%E8%A1%A1%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91/image-20201212142837427.png">
<meta property="og:image" content="https://jameslin23.gitee.io/2020/12/12/%E5%B9%B3%E8%A1%A1%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91/image-20201212143323528.png">
<meta property="og:image" content="https://jameslin23.gitee.io/2020/12/12/%E5%B9%B3%E8%A1%A1%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91/image-20201212143422067.png">
<meta property="og:image" content="https://jameslin23.gitee.io/2020/12/12/%E5%B9%B3%E8%A1%A1%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91/image-20201212144943468.png">
<meta property="og:image" content="https://jameslin23.gitee.io/2020/12/12/%E5%B9%B3%E8%A1%A1%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91/image-20201212151113598.png">
<meta property="og:image" content="https://jameslin23.gitee.io/2020/12/12/%E5%B9%B3%E8%A1%A1%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91/image-20201212151223612.png">
<meta property="og:image" content="https://jameslin23.gitee.io/2020/12/12/%E5%B9%B3%E8%A1%A1%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91/image-20201212152631233.png">
<meta property="og:image" content="https://jameslin23.gitee.io/2020/12/12/%E5%B9%B3%E8%A1%A1%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91/image-20201212153314487.png">
<meta property="og:image" content="https://jameslin23.gitee.io/2020/12/12/%E5%B9%B3%E8%A1%A1%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91/image-20201212153935525.png">
<meta property="og:updated_time" content="2020-12-15T02:08:31.855Z">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="平衡二叉搜索树">
<meta name="twitter:description" content="平衡二叉搜索树平衡二叉搜索树简称:BBST 平衡二叉搜索树类型  AVL树 Windows NT 内核中广泛使用  红黑树 C++ STL(比如map、set) java的TreeMap、TreeSet、HashMap、HashSet Linux的进程调度 Ngix的timer管理   AVL树平衡因子(Balance Factor): 某节点的左右子树的高度差 特点 每个节点的平衡因子只可能是1">
<meta name="twitter:image" content="https://jameslin23.gitee.io/2020/12/12/%E5%B9%B3%E8%A1%A1%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91/image-20201212141626132.png">
  
    <link rel="alternate" href="/atom.xml" title="JAVA" type="application/atom+xml">
  

  

  <link rel="icon" href="/css/images/mylogo.jpg">
  <link rel="apple-touch-icon" href="/css/images/mylogo.jpg">
  
    <link href="//fonts.googleapis.com/css?family=Source+Code+Pro" rel="stylesheet" type="text/css">
  
  <link href="https://fonts.googleapis.com/css?family=Open+Sans|Montserrat:700" rel="stylesheet" type="text/css">
  <link href="https://fonts.googleapis.com/css?family=Roboto:400,300,300italic,400italic" rel="stylesheet" type="text/css">
  <link href="//netdna.bootstrapcdn.com/font-awesome/4.0.3/css/font-awesome.css" rel="stylesheet">
  <style type="text/css">
    @font-face{font-family:futura-pt; src:url("/css/fonts/FuturaPTBold.otf") format("woff");font-weight:500;font-style:normal;}
    @font-face{font-family:futura-pt-light; src:url("/css/fonts/FuturaPTBook.otf") format("woff");font-weight:lighter;font-style:normal;}
    @font-face{font-family:futura-pt-italic; src:url("/css/fonts/FuturaPTBookOblique.otf") format("woff");font-weight:400;font-style:italic;}
}

  </style>
  <link rel="stylesheet" href="/css/style.css">

  <script src="/js/jquery-3.1.1.min.js"></script>
  <script src="/js/bootstrap.js"></script>

  <!-- Bootstrap core CSS -->
  <link rel="stylesheet" href="/css/bootstrap.css">

  
    <link rel="stylesheet" href="/css/dialog.css">
  

  

  
    <link rel="stylesheet" href="/css/header-post.css">
  

  
  
  
    <link rel="stylesheet" href="/css/vdonate.css">
  

</head>
</html>


  <body data-spy="scroll" data-target="#toc" data-offset="50">


  
  <div id="container">
    <div id="wrap">
      
        <header>

    <div id="allheader" class="navbar navbar-default navbar-static-top" role="navigation">
        <div class="navbar-inner">
          
          <div class="container"> 
            <button type="button" class="navbar-toggle" data-toggle="collapse" data-target=".navbar-collapse">
              <span class="sr-only">Toggle navigation</span>
              <span class="icon-bar"></span>
              <span class="icon-bar"></span>
              <span class="icon-bar"></span>
            </button>

            
              <a class="brand" style="border-width: 0;">
                <p>JAVA</p>
              </a>
            
            
            <div class="navbar-collapse collapse">
              <ul class="hnav navbar-nav">
                
                  <li> <a class="main-nav-link" href="/">首页</a> </li>
                
                  <li> <a class="main-nav-link" href="/archives">归档</a> </li>
                
                  <li> <a class="main-nav-link" href="/categories">分类</a> </li>
                
                  <li> <a class="main-nav-link" href="/tags">标签</a> </li>
                
                  <li> <a class="main-nav-link" href="/about">关于</a> </li>
                
                  <li><div id="search-form-wrap">

    <form class="search-form">
        <input type="text" class="ins-search-input search-form-input" placeholder>
        <button type="submit" class="search-form-submit"></button>
    </form>
    <div class="ins-search">
    <div class="ins-search-mask"></div>
    <div class="ins-search-container">
        <div class="ins-input-wrapper">
            <input type="text" class="ins-search-input" placeholder="请输入关键词...">
            <span class="ins-close ins-selectable"><i class="fa fa-times-circle"></i></span>
        </div>
        <div class="ins-section-wrapper">
            <div class="ins-section-container"></div>
        </div>
    </div>
</div>
<script>
(function (window) {
    var INSIGHT_CONFIG = {
        TRANSLATION: {
            POSTS: '文章',
            PAGES: '页面',
            CATEGORIES: '分类',
            TAGS: '标签',
            UNTITLED: '(无标题)',
        },
        ROOT_URL: '/',
        CONTENT_URL: '/content.json',
    };
    window.INSIGHT_CONFIG = INSIGHT_CONFIG;
})(window);
</script>
<script src="/js/insight.js"></script>

</div></li>
            </ul></div>
          </div>
                
      </div>
    </div>

</header>



      
            
      <div id="content" class="outer">
        
          <section id="main" style="float:none;"><article id="post-平衡二叉搜索树" style="width: 75%; float:left;" class="article article-type-post" itemscope itemprop="blogPost">
  <div id="articleInner" class="article-inner">
    
    
      <header class="article-header">
        
  
    <h1 class="thumb" itemprop="name">
      平衡二叉搜索树
    </h1>
  

      </header>
    
    <div class="article-meta">
      
	<a href="/2020/12/12/平衡二叉搜索树/" class="article-date">
	  <time datetime="2020-12-12T03:36:28.000Z" itemprop="datePublished">2020-12-12</time>
	</a>

      
    <a class="article-category-link" href="/categories/数据结构与算法/">数据结构与算法</a>

      
	<a class="article-views">
	<span id="busuanzi_container_page_pv">
		阅读量<span id="busuanzi_value_page_pv"></span>
	</span>
	</a>

      

    </div>
    <div class="article-entry" itemprop="articleBody">
      
        <h2 id="平衡二叉搜索树"><a href="#平衡二叉搜索树" class="headerlink" title="平衡二叉搜索树"></a>平衡二叉搜索树</h2><p>平衡二叉搜索树简称:<strong>BBST</strong></p>
<p><strong>平衡二叉搜索树类型</strong></p>
<ul>
<li><p><strong>AVL树</strong></p>
<p>Windows NT 内核中广泛使用</p>
</li>
<li><p><strong>红黑树</strong></p>
<p>C++ STL(比如map、set)</p>
<p>java的TreeMap、TreeSet、HashMap、HashSet</p>
<p>Linux的进程调度</p>
<p>Ngix的timer管理</p>
</li>
</ul>
<h2 id="AVL树"><a href="#AVL树" class="headerlink" title="AVL树"></a>AVL树</h2><p><strong>平衡因子(Balance Factor): 某节点的左右子树的高度差</strong></p>
<h3 id="特点"><a href="#特点" class="headerlink" title="特点"></a>特点</h3><ul>
<li>每个节点的平衡因子只可能是1、0、-1(如果绝对值-1,如果超过1,称为失衡)</li>
<li>每个节点的左右子树高度差不超过1</li>
<li>搜索、添加、删除的时间复杂度是o(logn)</li>
</ul>
<p><img src="https://jameslin23.gitee.io/2020/12/12/%E5%B9%B3%E8%A1%A1%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91/image-20201212141626132.png" alt="image-20201212141626132"></p>
<h3 id="旋转"><a href="#旋转" class="headerlink" title="旋转"></a>旋转</h3><p>调整旋转有4种情况</p>
<h4 id="LL-右旋转-单旋"><a href="#LL-右旋转-单旋" class="headerlink" title="LL-右旋转(单旋)"></a>LL-右旋转(单旋)</h4><p>当左子树出现不平衡情况，也就是LL(左节点-左节点)，就需要右旋转</p>
<ul>
<li>g.left = p.right</li>
<li>p.right = g</li>
<li>让P成为这个棵子树的根节点</li>
<li>仍然是一颗二叉搜索树: T0&lt; n &lt; T1 &lt; p &lt; T2 &lt; g &lt; T3</li>
</ul>
<p>需要注意的维护内容</p>
<ul>
<li>T2、p、g的parent属性</li>
<li>先后更新g、p的高度</li>
</ul>
<p><img src="https://jameslin23.gitee.io/2020/12/12/%E5%B9%B3%E8%A1%A1%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91/image-20201212142308077.png" alt="image-20201212142308077"></p>
<h4 id="RR-左旋转-单旋"><a href="#RR-左旋转-单旋" class="headerlink" title="RR - 左旋转(单旋)"></a>RR - 左旋转(单旋)</h4><p>当右子树出现不平衡情况，也就是RR(右节点-右节点)，就需要左旋转</p>
<ul>
<li>g.right = p.leftt</li>
<li>p.left = g</li>
<li>让p成为这棵子树的根节点</li>
<li>仍然是一颗二叉搜索树: T0 &lt; g &lt; T1 &lt; p &lt; T2 &lt;  n &lt;T3</li>
</ul>
<p>需要维护内容</p>
<ul>
<li>T1、p、g的parent属性</li>
<li>先后更新g、p的高度</li>
</ul>
<p><img src="https://jameslin23.gitee.io/2020/12/12/%E5%B9%B3%E8%A1%A1%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91/image-20201212142837427.png" alt="image-20201212142837427"></p>
<h4 id="LR-左旋转，右旋转"><a href="#LR-左旋转，右旋转" class="headerlink" title="LR-左旋转，右旋转"></a>LR-左旋转，右旋转</h4><p>出现LR情况、需要2次旋转，才能达到平衡</p>
<p><img src="https://jameslin23.gitee.io/2020/12/12/%E5%B9%B3%E8%A1%A1%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91/image-20201212143323528.png" alt="image-20201212143323528"></p>
<h4 id="RL-右旋转-左旋转"><a href="#RL-右旋转-左旋转" class="headerlink" title="RL-右旋转,左旋转"></a>RL-右旋转,左旋转</h4><p><img src="https://jameslin23.gitee.io/2020/12/12/%E5%B9%B3%E8%A1%A1%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91/image-20201212143422067.png" alt="image-20201212143422067"></p>
<h3 id="总结"><a href="#总结" class="headerlink" title="总结"></a>总结</h3><p><strong>添加</strong></p>
<ul>
<li>可能导致所有祖先节点都失衡</li>
<li>只要让高度最低的失衡节点恢复平衡,整棵树就恢复平衡[仅需o(1)次调整]</li>
</ul>
<p><strong>删除</strong></p>
<ul>
<li>只可能会导致父节点失衡</li>
<li>让父节点恢复平衡后,可能会导致更高层的祖先节点失衡[最多需要o(logn)次调整]</li>
</ul>
<p><strong>平均时间复杂度</strong></p>
<ul>
<li>搜索: o(logn)</li>
<li>添加:o(logn)，仅需o(1)次调整</li>
<li>删除:o(logn),最多需要o(logn)次旋转操作</li>
</ul>
<h2 id="红黑树"><a href="#红黑树" class="headerlink" title="红黑树"></a>红黑树</h2><h3 id="特点（5大特点）"><a href="#特点（5大特点）" class="headerlink" title="特点（5大特点）"></a>特点（5大特点）</h3><ul>
<li><strong>节点是RED或者BLACK</strong></li>
<li><strong>根节点是BLACK</strong></li>
<li><strong>叶子节点(外部节点,空节点) 都是BLACK</strong></li>
<li><strong>RED节点的子节点都是BLACK</strong><ul>
<li>RED节点的parent都是BLACK</li>
<li>从根节点到叶子节点的所有路径不能有2个连续的RED节点</li>
</ul>
</li>
<li><strong>从任一节点到叶子节点的所有路径都包含相同的BLACK节点</strong></li>
</ul>
<p><img src="https://jameslin23.gitee.io/2020/12/12/%E5%B9%B3%E8%A1%A1%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91/image-20201212144943468.png" alt="image-20201212144943468"></p>
<ul>
<li>红黑树和4阶B树(2-3-4树)具有等价性</li>
<li>BLACK节点与它的RED字节点融合在一起，形成1个B树节点</li>
<li>红黑树的BLACK节点个树与4阶B树的节点总个树相等</li>
</ul>
<h3 id="添加过程"><a href="#添加过程" class="headerlink" title="添加过程"></a>添加过程</h3><p>总共3大类，12种情况</p>
<ul>
<li><p>4种情况满足红黑情况的性质，不用修改。 <strong>父节点为黑色</strong></p>
<p><img src="https://jameslin23.gitee.io/2020/12/12/%E5%B9%B3%E8%A1%A1%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91/image-20201212151113598.png" alt="image-20201212151113598"></p>
</li>
<li><p>有八种情况满足红黑树性质：父节点为红色（Double Red）</p>
<p><img src="https://jameslin23.gitee.io/2020/12/12/%E5%B9%B3%E8%A1%A1%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91/image-20201212151223612.png" alt="image-20201212151223612"></p>
</li>
</ul>
<ul>
<li><p>其中4种叔父(<strong>父节点的兄弟</strong>)节点是黑色</p>
<p>这4种情况分别是RR/LL/RL/LR</p>
<p><strong>RR/LL</strong></p>
<p>1、父亲节点染成黑色BLACK,祖父节点染成RED</p>
<p>2、祖父节点进行单旋</p>
<p>3、RR(左旋)、LL(右旋)</p>
<p><img src="https://jameslin23.gitee.io/2020/12/12/%E5%B9%B3%E8%A1%A1%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91/image-20201212152631233.png" alt="image-20201212152631233"></p>
<p><strong>RL/LR</strong></p>
<p>1、自己染成黑色BLACK,祖父节点染成红色</p>
<p>2、进行双旋操作</p>
<p>3、LR(父节点左旋，祖父节点右旋)</p>
<p>4、RL(父节点右旋，祖父节点左旋)</p>
<p><img src="https://jameslin23.gitee.io/2020/12/12/%E5%B9%B3%E8%A1%A1%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91/image-20201212153314487.png" alt="image-20201212153314487"></p>
</li>
<li><p>4种叔父(<strong>父节点的兄弟</strong>)节点是红色</p>
<p>这4种情况也分别是RR/LL/RL/LR</p>
<p><strong>RR</strong></p>
<p>1、父节点和叔父节点染成黑色</p>
<p>2、祖父节点(染成红色)向上合并，当做新添加节点进行处理</p>
<p>3、向上合并时候有可能继续发生上益</p>
<p><img src="https://jameslin23.gitee.io/2020/12/12/%E5%B9%B3%E8%A1%A1%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91/image-20201212153935525.png" alt="image-20201212153935525"></p>
</li>
</ul>
<p>​    </p>
<h3 id="删除过程"><a href="#删除过程" class="headerlink" title="删除过程"></a>删除过程</h3><ul>
<li>A—删除的是叶子节点且该叶子节点是红色的，无需修复。</li>
<li>B—删除的是叶子节点且叶子节点是黑色的，会破坏特征5，需要修复</li>
<li>C—删除的节点（P）有一个子节点(S)，通过置换的方式，然后进行删除。<ul>
<li>S为红，P为黑，对应A情况</li>
</ul>
</li>
</ul>
<p>待补充（看算法导论为准）</p>
<h2 id="AVL树-VS-红黑树"><a href="#AVL树-VS-红黑树" class="headerlink" title="AVL树 VS 红黑树"></a>AVL树 VS 红黑树</h2><h3 id="总结-1"><a href="#总结-1" class="headerlink" title="总结"></a>总结</h3><p><strong>AVL树</strong></p>
<ul>
<li>平衡标准严格:每个左右子树的高度差不超过1</li>
<li>最大高度是1.44*log2(n+1)-1.328(100w节点，AVL树最大树高28)</li>
<li>搜索、添加、删除都是o(logn)复杂度，其中添加仅仅需要o(1)次调整、删除最多需要o(logn)次旋转调整</li>
</ul>
<p><strong>红黑树</strong></p>
<ul>
<li>平衡标准比较宽松:没有一条路径会大于其他路径2倍</li>
<li>最大高度是2*log2(n+1)(100万个节点，红黑树最大树高40)</li>
<li>搜索、添加、删除都是o(logn)复杂度，其中添加、删除都仅仅o(1)次旋转调整</li>
</ul>
<p><strong>选择</strong></p>
<ul>
<li>搜索的次数远远大于插入和删除,选择AVL树；搜索、插入、删除几乎差不多，选择红黑树</li>
<li>相对AVL树来说，红黑树牺牲了部分平衡以换取插入/删除操作时少量旋转操作，整体来说性能要优于AVL树</li>
<li>红黑树的平均统计性能优于AVL树,实际应用中更多选择使用红黑树</li>
</ul>

      
    </div>
    <footer class="article-footer">
      
        <div id="donation_div"></div>

<script src="/js/vdonate.js"></script>
<script>
var a = new Donate({
  title: '如果觉得我的文章对您有用，请随意打赏。您的支持将鼓励我继续创作!', // 可选参数，打赏标题
  btnText: '打赏支持', // 可选参数，打赏按钮文字
  el: document.getElementById('donation_div'),
  wechatImage: 'https://raw.githubusercontent.com/iTimeTraveler/iTimeTraveler.github.io/site/source/about/donate/images/WeChanQR.png',
  alipayImage: 'https://raw.githubusercontent.com/iTimeTraveler/iTimeTraveler.github.io/site/source/about/donate/images/AliPayQR.jpg'
});
</script>
      
      
      <div>
        <ul class="post-copyright">
          <li class="post-copyright-author">
          <strong>本文作者:  </strong>LeBron Tao
          </li>
          <li class="post-copyright-link">
          <strong>本文链接:  </strong>
          <a href="/2020/12/12/平衡二叉搜索树/" target="_blank" title="平衡二叉搜索树">https://jameslin23.gitee.io/2020/12/12/平衡二叉搜索树/</a>
          </li>
          <li class="post-copyright-license">
            <strong>版权声明:   </strong>
            本博客所有文章除特别声明外，均采用 <a rel="license" href="https://creativecommons.org/licenses/by-nc-nd/4.0/" target="_blank" title="Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0)">CC BY-NC-ND 4.0</a>
            许可协议。转载请注明出处
          </li>
         
        </ul>
<div>
</div></div>
      
      
        
	<div id="comment">
		<!-- 来必力City版安装代码 -->
		<div id="lv-container" data-id="city" data-uid="MTAyMC8yOTQ4MS82MDQ5">
		<script type="text/javascript">
		   (function(d, s) {
		       var j, e = d.getElementsByTagName(s)[0];

		       if (typeof LivereTower === 'function') { return; }

		       j = d.createElement(s);
		       j.src = 'https://cdn-city.livere.com/js/embed.dist.js';
		       j.async = true;

		       e.parentNode.insertBefore(j, e);
		   })(document, 'script');
		</script>
		<noscript>为正常使用来必力评论功能请激活JavaScript</noscript>
		</div>
		<!-- City版安装代码已完成 -->
	</div>



      
      
        
  <ul class="article-tag-list"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/数据结构与算法/">数据结构与算法</a></li></ul>

      

    </footer>
  </div>
  
    
<nav id="article-nav">
  
    <a href="/2020/12/14/TCP-IP/" id="article-nav-newer" class="article-nav-link-wrap">
      <strong class="article-nav-caption">上一篇</strong>
      <div class="article-nav-title">
        
          TCP-IP
        
      </div>
    </a>
  
  
    <a href="/2020/12/11/ZooKeeper的ZAB协议/" id="article-nav-older" class="article-nav-link-wrap">
      <strong class="article-nav-caption">下一篇</strong>
      <div class="article-nav-title">ZooKeeper的ZAB协议</div>
    </a>
  
</nav>

  
</article>

<!-- Table of Contents -->

  <aside id="toc-sidebar">
    <div id="toc" class="toc-article">
    <strong class="toc-title">文章目录</strong>
    
        <ol class="nav"><li class="nav-item nav-level-2"><a class="nav-link" href="#平衡二叉搜索树"><span class="nav-number">1.</span> <span class="nav-text">平衡二叉搜索树</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#AVL树"><span class="nav-number">2.</span> <span class="nav-text">AVL树</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#特点"><span class="nav-number">2.1.</span> <span class="nav-text">特点</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#旋转"><span class="nav-number">2.2.</span> <span class="nav-text">旋转</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#LL-右旋转-单旋"><span class="nav-number">2.2.1.</span> <span class="nav-text">LL-右旋转(单旋)</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#RR-左旋转-单旋"><span class="nav-number">2.2.2.</span> <span class="nav-text">RR - 左旋转(单旋)</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#LR-左旋转，右旋转"><span class="nav-number">2.2.3.</span> <span class="nav-text">LR-左旋转，右旋转</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#RL-右旋转-左旋转"><span class="nav-number">2.2.4.</span> <span class="nav-text">RL-右旋转,左旋转</span></a></li></ol></li><li class="nav-item nav-level-3"><a class="nav-link" href="#总结"><span class="nav-number">2.3.</span> <span class="nav-text">总结</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#红黑树"><span class="nav-number">3.</span> <span class="nav-text">红黑树</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#特点（5大特点）"><span class="nav-number">3.1.</span> <span class="nav-text">特点（5大特点）</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#添加过程"><span class="nav-number">3.2.</span> <span class="nav-text">添加过程</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#删除过程"><span class="nav-number">3.3.</span> <span class="nav-text">删除过程</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#AVL树-VS-红黑树"><span class="nav-number">4.</span> <span class="nav-text">AVL树 VS 红黑树</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#总结-1"><span class="nav-number">4.1.</span> <span class="nav-text">总结</span></a></li></ol></li></ol>
    
    </div>
  </aside>

</section>
        
      </div>
      
      <footer id="footer">
  

  <div class="container">
      	<div class="row">
	      <p> Powered by <a href="http://hexo.io/" target="_blank">Hexo</a> and <a href="https://github.com/iTimeTraveler/hexo-theme-hiker" target="_blank">Hexo-theme-hiker</a> </p>
	      <p id="copyRightEn">Copyright &copy; 2013 - 2021 JAVA All Rights Reserved.</p>
	      
	      
    		<p class="busuanzi_uv">
				访客数 : <span id="busuanzi_value_site_uv"></span> |  
				访问量 : <span id="busuanzi_value_site_pv"></span>
		    </p>
  		   
		</div>

		
  </div>
</footer>


<!-- min height -->

<script>
    var wrapdiv = document.getElementById("wrap");
    var contentdiv = document.getElementById("content");
    var allheader = document.getElementById("allheader");

    wrapdiv.style.minHeight = document.body.offsetHeight + "px";
    if (allheader != null) {
      contentdiv.style.minHeight = document.body.offsetHeight - allheader.offsetHeight - document.getElementById("footer").offsetHeight + "px";
    } else {
      contentdiv.style.minHeight = document.body.offsetHeight - document.getElementById("footer").offsetHeight + "px";
    }
</script>
    </div>
    <!-- <nav id="mobile-nav">
  
    <a href="/" class="mobile-nav-link">Home</a>
  
    <a href="/archives" class="mobile-nav-link">Archives</a>
  
    <a href="/categories" class="mobile-nav-link">Categories</a>
  
    <a href="/tags" class="mobile-nav-link">Tags</a>
  
    <a href="/about" class="mobile-nav-link">About</a>
  
</nav> -->
    

<!-- mathjax config similar to math.stackexchange -->

<script type="text/x-mathjax-config">
  MathJax.Hub.Config({
    tex2jax: {
      inlineMath: [ ['$','$'], ["\\(","\\)"] ],
      processEscapes: true
    }
  });
</script>

<script type="text/x-mathjax-config">
    MathJax.Hub.Config({
      tex2jax: {
        skipTags: ['script', 'noscript', 'style', 'textarea', 'pre', 'code']
      }
    });
</script>

<script type="text/x-mathjax-config">
    MathJax.Hub.Queue(function() {
        var all = MathJax.Hub.getAllJax(), i;
        for(i=0; i < all.length; i += 1) {
            all[i].SourceElement().parentNode.className += ' has-jax';
        }
    });
</script>

<script type="text/javascript" src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
</script>


  <link rel="stylesheet" href="/fancybox/jquery.fancybox.css">
  <script src="/fancybox/jquery.fancybox.pack.js"></script>


<script src="/js/scripts.js"></script>




  <script src="/js/dialog.js"></script>








	<div style="display: none;">
    <script src="https://s95.cnzz.com/z_stat.php?id=1260716016&web_id=1260716016" language="JavaScript"></script>
  </div>



	<script async src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js">
	</script>






  </div>

  <div class="modal fade" id="myModal" tabindex="-1" role="dialog" aria-labelledby="myModalLabel" aria-hidden="true" style="display: none;">
  <div class="modal-dialog">
    <div class="modal-content">
      <div class="modal-header">
        <h2 class="modal-title" id="myModalLabel">设置</h2>
      </div>
      <hr style="margin-top:0px; margin-bottom:0px; width:80%; border-top: 3px solid #000;">
      <hr style="margin-top:2px; margin-bottom:0px; width:80%; border-top: 1px solid #000;">


      <div class="modal-body">
          <div style="margin:6px;">
            <a data-toggle="collapse" data-parent="#accordion" href="#collapseOne" onclick="javascript:setFontSize();" aria-expanded="true" aria-controls="collapseOne">
              正文字号大小
            </a>
          </div>
          <div id="collapseOne" class="panel-collapse collapse" role="tabpanel" aria-labelledby="headingOne">
          <div class="panel-body">
            您已调整页面字体大小
          </div>
        </div>
      


          <div style="margin:6px;">
            <a data-toggle="collapse" data-parent="#accordion" href="#collapseTwo" onclick="javascript:setBackground();" aria-expanded="true" aria-controls="collapseTwo">
              夜间护眼模式
            </a>
        </div>
          <div id="collapseTwo" class="panel-collapse collapse" role="tabpanel" aria-labelledby="headingTwo">
          <div class="panel-body">
            夜间模式已经开启，再次单击按钮即可关闭 
          </div>
        </div>

        <div>
            <a data-toggle="collapse" data-parent="#accordion" href="#collapseThree" aria-expanded="true" aria-controls="collapseThree">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;关 于&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</a>
        </div>
         <div id="collapseThree" class="panel-collapse collapse" role="tabpanel" aria-labelledby="headingThree">
          <div class="panel-body">
            JAVA
          </div>
          <div class="panel-body">
            Copyright © 2021 LeBron Tao All Rights Reserved.
          </div>
        </div>
      </div>


      <hr style="margin-top:0px; margin-bottom:0px; width:80%; border-top: 1px solid #000;">
      <hr style="margin-top:2px; margin-bottom:0px; width:80%; border-top: 3px solid #000;">
      <div class="modal-footer">
        <button type="button" class="close" data-dismiss="modal" aria-label="Close"><span aria-hidden="true">×</span></button>
      </div>
    </div>
  </div>
</div>
  
  <a id="rocket" href="#top" class=""></a>
  <script type="text/javascript" src="/js/totop.js?v=1.0.0" async=""></script>
  
    <a id="menu-switch"><i class="fa fa-bars fa-lg"></i></a>
  
</body>
</html>